<?php


class SetCover {
	
	private $subsets;
	private $weights;
	private $universe;
	
	public function __construct($fileName) {
		$this->subsets = array();
		$this->universe = range(1, 100, 1);
		$this->readFile($fileName);
	}
		
	public function getSet() {
		
		return $this->subsets;
	}
	
	public function getWeights() {
		
		return $this->weights;
	}
	
	public function findMinimumSetCover($weighted = false) {
		$uncoveredSets = $this->universe;
		$coveringSets = array();
		
		
		while (count($uncoveredSets) > 0) {
			// Find subset with maximum intersect
			list($index, $maxCoveringSubset) = $this->findMaxCoveringSubset($uncoveredSets, $weighted);
			
			if (count($maxCoveringSubset) > 0) {
				$uncoveredSets = array_diff($uncoveredSets, $maxCoveringSubset);
				$coveringSets[$index] = $maxCoveringSubset;
			} else {
				break;
			}
		}
		
		return $coveringSets;
	}
	
	protected function findMaxCoveringSubset(array $uncoveredSets, $weighted = false) {
		$maxWeight = 0;
		$maxCoveringSubset = array();
		$index = 1;
		
		foreach ($this->subsets as $i => $subset) {
			$intersect = array_intersect($uncoveredSets, $subset);
			$weight = count($intersect);
			
			if ($weight != 0) {
				if ($weighted) {
					// @FIXME: is this correct?
					$weight = $this->weights[$i] / $weighted;
				}
					
				if ($maxWeight < $weight) {
					$maxWeight = $weight;
					$maxCoveringSubset = $subset;
					$index = $i;
				}
			}
		}
		
		return array($index, $maxCoveringSubset);
	}
	
	
	public function readFile($fileName) {
		$file = fopen($fileName, 'r');
		$header = fgets($file);
		$count = 1;
		while(!feof($file)) {
			$line = fgets($file);
			$row = preg_split('/\s+/', $line);
			
			if (count($row) < 2) {
				break;
			}
			array_shift($row);
			$weight = (float) (mb_substr(array_shift($row), 2)); // Remove the "w=" part, and retrieve weight

			$subset = array();			
			foreach ($row as $element) {
				if ($element != null) {
					$subset[] = $element;
				}
			}
			
			$this->subsets[$count] = $subset;
			$this->weights[$count] = $weight;
			
			$count++;
		}
		
		fclose($file);
	}
}